#        Arvore de livros         /\
#                                //\\
#  Grupo: Gustavo Pereira       ///\\\
#         Mario Fernandes      ////\\\\
#         Rafaella Leandra        ||

class Nodo():
    def __init__(self, Valor, Pai = None, Esquerdo = None, Direito = None, Usuario = None):
        self.Vermelho = True
        self.Dado = Valor
        self.Pai = Pai
        self.Esquerdo = Esquerdo
        self.Direito = Direito
        self.Usuario = Usuario  #Usuario com o livro

    def Nodo_vermelho(self): #pergunta True False
        return self.Vermelho
    
    def setPreto(self):
        self.Vermelho = False
    
    def setVermelho(self):
        self.Vermelho = True
    
    def getAvo(self):
        if self.Pai == None:
            return None
        else:
            return self.Pai.Pai
    
    def getPai(self):
        return self.Pai

    def getTio(self):
        if self.getAvo() != None:
            if self.getPai() == self.getAvo().Direito:
                return self.getAvo().Esquerdo #Tio
            elif self.getPai() == self.getAvo().Esquerdo:
                return self.getAvo().Direito
            else:
                return None

    def printCOR(self):
        if self.Vermelho == True:
            return "VERMELHO"
        else:
            return "PRETO"
         
#------------------------------------- Funcoes do EMPRESTIMO
    def Emprestar_Livro(self,Usuario): 
        self.Usuario = Usuario

        
    def Devolver_Livro(self,Usuario):
        if self.Usuario == Usuario:
            self.Usuario = None #Livro Devolvido
            return True
        else:
            return False
        
    def Disponivel(self): #Pergunta se Livro esta disponivel
        if self.Usuario == None:
            return True
        else:
            return False
        
#------------------------------------- Funcoes do EMPRESTIMO

    def isLeft(self): #isleft
        if self.Pai == None: #Arvore vazia
            return None
        if self.Pai.Esquerdo != None: 
            return self.Pai.Esquerdo.Dado == self.Dado
        return False

class AVP_Livros():
    def __init__(self):
        self.Raiz = None
        
    def Pesquisar(self, No, Valor): #interativo
        while No != None and Valor != No.Dado:
            if Valor < No.Dado:
                No = No.Esquerdo
            else: 
                No = No.Direito
        return No


        while No != None and Valor != No.Dado:
            if Valor < No.Dado:
                No = No.Esquerdo
            else: 
                No = No.Direito
        return No

#-----------------------------------------DELETE
#    def Menor(self, arvore):
#        no = arvore.Esquerdo
#        if no != None:
#            while no.Esquerdo != None:
#                no = no.Esquerdo
#        else: 
#            no = arvore
#        return no
#    
#    def Sucessor(self, arvore):
#        return self.Menor(arvore.Direito) 
#    
#    def Deletar(self,Valor):
#        if self.Raiz != None:
#            self.Excluir(Valor)
#    
#    def Excluir(self,No):
#        if No.Esquerdo == None or No.Direito == None:
#            Y = No
#        else:
#            Y = Sucessor(No)
#        if Y.Esquerdo != None:
#            X = Y.Esquerdo
#        else:
#            X = Y.Direito
#        X.Pai = Y.Pai
#        if Y.Pai == None:
#            self.Raiz = X
#            if Y == Y.Pai.Esquerdo:
#                Y.Pai.Esquerdo = X
#            else:
#                Y.Pai.Direita = X
#        if Y != No:
#            No.Dado = Y.Dado
##        if Y.Nodo_vermelho == False:
##            Excluir_FIX(self,No)
#        return Y
#        
##    def Excluir_FIX(self,No):
##        while 
            
#-----------------------------------------DELETE           
     
    def Inserir(self, Valor):
        if self.Raiz == None:
            self.Raiz = Nodo(Valor)
            self.Raiz.setPreto()
            return
        self.Adicionar(Valor,self.Raiz)

    def Adicionar(self, Valor, No = None): 
        if Valor < No.Dado:                         #Adicionar na Esquerda
            if No.Esquerdo == None:
                V = Nodo(Valor, Pai=No)
                No.Esquerdo = V
                self.Inserir_FIX(V) 
            else:
                self.Adicionar(Valor, No.Esquerdo)
        elif Valor >= No.Dado:                       #Adicionar na Direita
            if No.Direito == None:
                V = Nodo(Valor, Pai=No)
                No.Direito = V
                self.Inserir_FIX(V) 
            else:
                self.Adicionar(Valor, No.Direito)
        else:
            print("\nLivro Ja esta cadastrado")
                                                                    
    def Inserir_FIX(self, No): 
        if No.Pai == None:
            No.setPreto()
            return
        
        if not No.Pai.Nodo_vermelho():
            return
        
        if No.getTio() != None and No.getTio().Nodo_vermelho():
            No.getTio().Vermelho = False
            No.Pai.Vermelho = False
            self.Inserir_FIX(No.getAvo())
            return
        self.Rotacionar(No) 

    def Rotacionar(self, No):   #Rotacionar
        if No.isLeft():
            if No.Pai.isLeft(): # Dupla rotacao a esquerda 
                self.Rotacionar_Direita(No.Pai, False)
            else:
                self.Rotacionar_Esquerda(No, True)
        else:                                           #Direita
            if No.Pai.isLeft():
                self.Rotacionar_Direita(No, True)
            else:                                       #Dupla rotacao a direita 
                self.Rotacionar_Esquerda(No.Pai, False)
            

    def Rotacionar_Esquerda(self, No, Girar=False):
        A = No
        B = A.Pai
        if Girar == True:
            C = A.Pai
            B = C.Pai
            B.Direito = A
            A.Pai = B
            C.Esquerdo = A.Direito
            if A.Direito != None:
                A.Direito.Pai = C
            A.Direito = C
            C.Pai = A
        D = B.Pai
        E = B.isLeft()    
        B.Direito = A.Esquerdo
        if B.Direito != None:
            B.Direito.Pai = B
        A.Esquerdo = B
        B.Pai=A
        B.setVermelho()
        A.setPreto()
        if D == None:
            A.Pai = None
            self.Raiz = A
        elif D != None and E:
            A.Pai=D
            D.Esquerdo=A
            D.setVermelho()
            self.Inserir_FIX(D)
        else:
            A.Pai=D
            D.Direito=A
            D.setVermelho()
            self.Inserir_FIX(D)

    def Rotacionar_Direita(self, No, Girar=False): 
        A = No
        B = A.Pai
        if Girar == True:
            C = A.Pai    
            B = C.Pai
            C.Direito = A.Esquerdo
            if A.Esquerdo != None:
                C.Direito.Pai = C
            B.Esquerdo = A
            A.Pai = B
            A.Esquerdo = C
            C.Pai = A
                
        D = B.Pai
        E = B.isLeft()
        B.Esquerdo = A.Direito
        if A.Direito != None:
            A.Direito.Pai = B
        A.Direito = B
        B.Pai = A
        B.setVermelho()
        A.setPreto()
        if D == None:
            A.Pai = None
            self.Raiz = A
        elif D != None and E:
            A.Pai = D
            D.Esquerdo = A
            D.setVermelho()
            self.Inserir_FIX(D)
        else:
            A.Pai = D
            D.Direito = A
            D.setVermelho()
            self.Inserir_FIX(D)
            
    def Imprimir_Arvore(self, No=None): #NA ORDEM
        No2=No
        if No == None:
            No2 = self.Raiz
        if No2.Esquerdo != None:
            self.Imprimir_Arvore(No2.Esquerdo)
        print "Disponivel:%s Cor:%s  Livro:(%s)" %(No2.Disponivel(),No2.printCOR(),No2.Dado)
        if No2.Direito != None:
            self.Imprimir_Arvore(No2.Direito)        

#TESTS
#USER=AVP_Livros()
#USER.Inserir("HARRY")
#USER.Inserir("ANDY")
#USER.Inserir("HUNGER")
#USER.Inserir("WHATS UP")
#USER.Inserir("A DAY")
#USER.Imprimir_Arvore()
#
#print "-----------------------------"
##print USER.Sucessor(USER.Raiz).Dado
#
#result1 = USER.Pesquisar(USER.Raiz,"HARRY")
#result1.Emprestar_Livro("Gustavo")
#print result1.Usuario,result1.Dado
#result1 = USER.Pesquisar(USER.Raiz,"HUNGER")
#result1.Emprestar_Livro("Mario")
#print result1.Usuario,result1.Dado
#result1 = USER.Pesquisar(USER.Raiz,"ANDY")
#result1.Emprestar_Livro("Rafa")
#print result1.Usuario,result1.Dado
#
#print "-----------------------------"
#USER.Imprimir_Arvore()

